package com.chapter2.sort;

/** 
 * @ClassName: Quick3Way 
 * @Description:快速排序--三向切分
 * 
 * 标准快速排序的切分是二向切分，将切分的标记值移动到了中间。但是如果有很多重复元素，这种二向切分很低效。他可能会使得切分值大多比较靠左或者靠右，而且会导致很多重复切分某个标记值。
 * 而三向切分目的就是希望小的都往左边靠，大的都往右边靠，标记值相等的全部占中间
 * 
 * @author minjun minjun@bw30.com
 * @date 2015-2-16 下午9:38:19 
 *  
 */
public class Quick3Way extends QuickSort{
	
	/**
	 * 重写关键的排序和切分的步骤
	 * 
	 * 由于是三向切分，所以不能如同之前一样返回 一个切分后的索引位置，因为这时索引位置可能很多，是一个范围。所以采取的策略就是直接在排序的主方法里面切分，切分完毕后，拿到两边的索引，递归继续切分
	 * 
	 */
	@Override
	protected void sort(int[] array, int start, int end) {
		if(start>=end) return;
		int s=start;
		int i=s+1;
		int j=end;
		//切分值
		int k=array[start];
		while(i<=j){
			if(less(array[i], k)) 		exchange(array, i++, s++);//如果轮询到的元素比切分标记值小，那么往左边放 
			else if(less(k, array[i])) 	exchange(array, i, j--);//如果比标记值大，那么往右边放
			else 						i++;//如果相等，继续移动左边的指针
		}
		//递归调用左边的与右边的进行切分
		sort(array, start, s-1);
		sort(array, j+1, end);
	}

}
